APL (an acronym for A Programming Language) is a computer programming language based on a varied set of predefined functions referred to as "primitive functions". A primitive function may be viewed as a function which corresponds to a single character on an APL keyboard or an "operator" applied to such a character, Some primitive functions represent fundamental mathematical operators (such as addition, subtraction, raising a number to a power, and the like). Other primitive functions involve logical operations, matrix operations, and data assignment operations. Primitive functions perform various operations ranging from reordering lists numerically or alphabetically, to changing a scalar value to a vector, to restructuring a matrix or array, or displaying specified information--operations or functions useful in business, scientific, and character processing applications. A list of primitive functions and explanations thereof are set forth in a publication entitled APL--360 Primer, Third Edition, (IBM Publication Number GH20-0689-2) written by Paul Berry, 1971. Detailed description of the APL language is also provided in APL An Interation Approach, Second Edition, by Leonard Gilman and Allen Rose, John Wiley and Sons, Inc., 1974. Additional information on APL language for users of APL Systems is found in Systems--APL Language, Sixth Edition, (IBM Publication Number GC26-3847-5), 1983, and the principles underlying its development are given in a paper by A. D. Falkoff and K. E. Iversion entitled "The Design of APL", IBM Journal of Research and Development, Vol. 17, No. 4, Jul., 1973.
Primitive functions are typically characterized by a valence which suggests the number of arguments on which the primitive function is to operate. When a primitive function operates on just one argument, it is styled as "Monadic". When a primitive function is to operate on two arguments, the primitive function is referred to as .-+.Dyadic". In Monadic form, the argument is positioned to the right of the symbol representing the primitive function. In Dyadic form, one argument is positioned to the left and the other argument is positioned to the right of the primitive function symbol.
Oftentimes the same APL primitive function has a Monadic meaning and a Dyadic meaning. For example, the Greek letter iota (.iota.) when applied to only one argument represents an "index" function. The index function .iota.n defines a string of numbers starting with one and incrementing up to the value n. .iota.5 then corresponds to 1 2 3 4 5. When .iota. is preceded and followed by an argument, it is Dyadic and represents an "indexing" or "ranking" function. That is, the Dyadic .iota. is used to determine where, in the array of the left argument each element of the right argument is positioned. For example, if X is a vector including the alphabet with "A" being in the first position, "B" being the second position, etc., the expression X .iota.`ABACUS` would yield a result 1 2 1 3 21 19. Similarly, 1 3 .iota.3 1 1 would yield a result 2 1 1 (where "3" is in the second position of the left argument.)
Some functions are derived from the primitive functions and are available in the APL language. These derived functions are typically formed from primitive functions (including operators) and may involve several operations. For example, +/ represents a derived function wherein at all values to the right thereof are summed. Other derived functions include matrix products and the like, wherein matrix elements may undergo several functions--such as multiplication and summation--before the desired result is evaluated. Primitive functions and derived functions are hereinafter referred to collectively as "basic functions".
The arguments that are operated on may be of several types: integer, real, complex, Boolean, or (alphanumeric) characters, for example. Each argument is also characterized in terms of its "rank" and "shape". "Rank" represents the n umber of dimensions, or axes, in a data item; and "shape" reflects the number of elements along the various dimensions or axes. An argument may be in the form of a "scalar" having no dimensions and hence a rank of zero; a "vector" having one dimension and hence a rank of one; a "matrix" having two dimensions and hence a rank of two; or an array having more than two dimensions. For a vector, the shape corresponds to the number of elements in its single dimension; for a matrix, the shape corresponds to the number of rows and the number of columns; and for a larger array, the shape corresponds to the number of elements in the respective dimensions.
In APL programming, primitive functions and derived functions may be used by themselves to perform desired operations or may serve as building blocks that can be combined by a programmer to form user-defined functions. When a user defines a function, it may be "called" in the same way that a primitive function or derived function is. That is, by specifying arguments (as required) and including an appropriate reference to the function, the user-defined function may be executed as if it were a primitive function or derived function.
At this point is it noted that APL has two distinct modes. In a definitional mode, the user can form his (or her) own definitions or functions. When in the definitional mode, the computer operates to store the entered definitions or function. The second mode is an execution mode in which expressions (including primitive functions, derived functions, or defined functions together with arguments and parameters therefor) are processed by the computer. When in the execution mode, the computer executes one expression (or instruction) after another as each line is entered by the user. The result is then immediately communicated to the user.
The defining of customized functions by the user and the immediate execution of expressions represent significant attractive features of APL. Because the user interacts with the computer system, the user enjoys great flexibility in revising and re-directing his (or her) computer program as results are returned and is able to stop his (or her) program at a desired point to enter data.
Another significant aspect of APL is that the language per se does not distinguish variables based on types or internal representations. For example, from the language itself, it cannot be determined whether a variable is an integer or a real number; however the internal representation and processing of each within the computer is quite different. Instead, type (and internal representation) is inferred from use. Moreover, the type of a given variable may change from time to time during an application program; however, although the change is recognized by the computer the change is not manifested in the programming code. While facilitating the writing of code is APL, the lack of differentiation between variable types and the changing of variables from one type to another result in a dynamic instability which makes the tracking of variables in a translation process difficult.
The dynamic, potentially unstable nature of APL objects has prompted most APL implementations to be interpretive in nature. An "interpreter" seeks to execute code directly without any intermediate language, typically performing syntax analysis and argument-conformability and domain checking on every execution of an APL statement or expression. By executing sequentially, the interpreter need not consider how a variable may have changed in type. It is the current status of variables--as determined by earlier executed instructions--which need be considered.
A significant problem with interpretation is a considerably high overhead in execution and storage costs, especially for statements involving arguments that include few elements. Hence, for a number of years, efforts have been made to overcome such inherent performance limitations of APL interpretation.
An alternative to interpretation is translation or complication. In a general sense, the term "translator" in computer science parlance means a program which transforms software from one computer language to another. A "high level APL translator" thus means a program which transforms all or some code in an APL application into code in a high level computer language, such as FORTRAN. Although sometimes assigned a broader scope, the term "compiler" is normally applied to a translator that prepares machine language code from code written in a higher level language. For purposes of this description, the terms "translation" and "compilation" are used to accordance with the definitions set forth hereinabove. In further defining compilation, it is noted that if APL is transformed directly to machine language form, that is clearly compilation. Moreover, if APL is first transformed to a language such as FORTRAN by a high level translator and the resulting FORTRAN is transformed to machine code by a FORTRAN compiler, this total process of re-forming the APL into machine language form is compilation also.
In the past, compiling APL has typically involved the examining of APL code with the APL statement being the unit of compilation. Such one-statement-at-a-time compiling results in a weak form of static analysis. This shortcoming may be overcome by use of declarations in which the user sends informational messages to the computer; however, the required number of declarations for the statement-by-statement approach is impractically large.
High level translators of the prior technology generally define the APL function (rather than the APL statement) as the unit of translation. However, most of these high level translators do not include a rank and storage type analysis and perform little or no static analysis. Consequently, prior art high level translators either produce such general code as to provide little advantage, if any, over APL interpreters or severely limit the subset of APL operations or functions that can be translated. Such limitations have made it difficult to partition APL applications into sections to be translated and sections to be interpreted. Moreover, the generality of such approaches have normally required the user to include numerous declarations.
Notwithstanding the widespread use of APL in varied applications and the numerous continued efforts in enhancing the processing of APL programs by translation (e.g., compiling or high level translating) rather than interpreting, no overall satisfactory approach has been suggested by the prior art.
Some references in the prior technology discuss APL translation, including compilation. Such prior technology fails to adequately account for the various cases which can apply to the APL primitive functions and derived functions or fail to overcome the difficulty of translating variables which the language does not distinguish based on type (i.e., internal representation). Moreover, the prior art does not provide methodology for deriving shape information--which severely limits translation or compilation.
The following U.S. Patents relate to computer program translation in general. U.S. Pat. No. 4,374,408 discloses a multi-pass system for translating an RPG program to COBOL. U.S. Pat. No. 4,309,756 discloses a method of automatically evaluating source language logic condition sets and compiling machine executable instructions directly therefrom. These patent references are cited as of background interest.